#include <iostream>

// todo 用 string 来实现任意位数 暂时不做这个
// 求 a 的 m 次方 mod n
int QuickMod(int a, int m, int n)
{
    // 把 m 转化为二进制
    int mBin[32] = { 0 };
    for(size_t i = 0; i < 32; ++i)
    {
        mBin[i] = (m >> (31 - i)) & 1;
    }
    int result = 1;
    int tmp = a;
    for(size_t i = 0; i < 32; ++i)
    { 
        if(mBin[i] != 0)
        {
            result = (result * tmp) % n;
        }
        tmp = ((tmp % n) * (tmp % n)) % n;
    }
    return result % n;
}


// // 递归版本
// int MaxCommonDivisor(int a, int b)
// {
//     if(a < b)
//     {
//         std::swap(a, b);
//     }
//     if(a % b == 0)
//     {
//         return b;
//     }
//     return MaxCommonDivisor(b, a % b);
// }

// 非递归
int MaxCommonDivisor(int a, int b)
{
    if(a < b)
    {
        std::swap(a, b);
    }
    int t = 1;
    while(b)
    {
        t = a % b;
        a = b;
        b = t;
    }
    return a;

}
//扩展欧几里得算法
int ExpendMaxCommonDivisor(int a,int b,int &x,int &y)
{
    if(b == 0)
    {
        x=1; y=0;
        return a;
    }
    // 核心 a * x + b * y = gcd = b * x1 + (a % b) * y1  x1 y1为下层递归的变量
    // 由于 a % b = a - (a / b) * b 因为 a % b 是一个不可逆的过程 所以用算式求得
    // 带入得到 a * x + b * y = b * x1 + a * y1 - (a / b) * b * y1
    // 匹配得到 x = y1 y = x1 - (a / b) * y1 从而往上层递归
    int r = ExpendMaxCommonDivisor(b, a%b, x, y);
    int temp = y;    //把x y变成上一层的
    y = x - (a/b) * y;
    x = temp;
    return r;     //得到a b的最大公因数
}





int main()
{

    int x = 0;
    int y = 0;
    int a = 0;
    int b = 0;
    int c = 0;
    std::cin >> a >> b >> c;
    // std::cout << ExpendMaxCommonDivisor(a, b, x, y) << std::endl;
    // std::cout << "x: " << x << " y: " << y << std::endl;
    std::cout << QuickMod(a, b, c) << std::endl;
    return 0;
}
